package com.heima.leetcode.practice;

import java.util.LinkedList;

/**
 * 993. 二叉树的堂兄弟节点
 * @author 勾新杰
 * @version 1.0
 * @date 2024/10/15 9:20
 */
public class E993 {

    /**
     * 用层序遍历解决
     * @param root 根节点
     * @param x 节点x
     * @param y 节点y
     * @return 如果x和y是堂兄弟节点，则返回true；否则返回 false。
     */
    @SuppressWarnings("all")
    public boolean isCousins(TreeNode root, int x, int y) {
        int parentX = -1;
        int parentY = -1;
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode poll = queue.poll();
                if (poll.left != null){
                    if (poll.left.val == x){
                        parentX = poll.val;
                    } else if (poll.left.val == y) {
                        parentY = poll.val;
                    }
                    queue.offer(poll.left);
                }
                if (poll.right != null){
                    if (poll.right.val == y){
                        parentY = poll.val;
                    } else if (poll.right.val == x) {
                        parentX = poll.val;
                    }
                    queue.offer(poll.right);
                }
            }
            // 当前层两个都没好到
            if (parentX == -1 && parentY == -1){
                continue;
            }
            // 当前层只有一个找到
            else if (parentX == -1 || parentY == -1) {
                return false;
            }
            /// 当前层两个都找到了
            else{
                return parentX != parentY;
            }
        }
        // 遍历完每一层都没有找到这两个节点
        return false;
    }
}
